package binarysearch.test4;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/12 11:18
 */
public class Solution1 {

    // 二分查找思想
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        return bs(nums1, nums2);
    }

    private double bs(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) {
            return bs(B, A);
        }
        int l = 0;
        int r = m;
        while (l <= r) {
            int i = l + ((r - l) >> 1);
            int j = (m + n + 1) / 2 - i;
            if (i != 0 && j != n && A[i - 1] > B[j]) {
                // 此时i位置应该调小一点
                r = i - 1;
            } else if (j != 0 && i != m && B[j - 1] > A[i]) {
                // 此时i位置应该调大一点
                l = i + 1;
            } else {
                // 满足要求了
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - 1];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }

                if (((m + n) & 1) == 1) return maxLeft;

                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(A[i], B[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}
